// Package day_10_KMP_manacher manacher
// @Title day_10_KMP_manacher
// @Description
// @Author  == 琳琳也叫王木木 ==  2021/9/3 16:55
// @Create  2021/9/3 16:55
package day_10_KMP_manacher

import "math"

func manacherString(str string) []byte {
	res := make([]byte, len(str)*2+1)
	index := 0
	for i := 0; i != len(res); i++ {
		if (i & 1) == 0 {
			res[i] = '#'
		} else {
			res[i] = str[index]
			index++
		}
	}
	return res
}

// MaxPalindromeStringLen 返回最长回文子字符串的长度
func MaxPalindromeStringLen(s string) int {
	if s == "" || len(s) < 1 {
		return 0
	}
	charArr := manacherString(s) // 单纯的给字符串加上分隔符 1221 -> #1#2#2#1#
	//fmt.Println(charArr)
	pArr := make([]int, len(charArr)) // 这个是回文半径数组  和被处理串的长度一样
	C := -1                           // 中心点
	R := -1                           // 回文右边界再往右边一个位置， 最右的有效区域是R-1位置
	max := -1
	for i := 0; i != len(charArr); i++ {
		// i为中心向左右两遍扩展 至少多大的回文区域 先给pArr[i] (i在R外)
		if R > i {
			// i 在 R 内
			pArr[i] = int(math.Min(float64(pArr[2*C-i]), float64(R-i)))
		} else {
			// i 在 R 外
			pArr[i] = 1
		}
		for i+pArr[i] < len(charArr) && i-pArr[i] > 1 {
			if charArr[i+pArr[i]] == charArr[i-pArr[i]] {
				pArr[i]++
			} else {
				break
			}
		}
		if i+pArr[i] > R {
			R = i + pArr[i]
			C = i
		}
		max = int(math.Max(float64(max), float64(pArr[i])))
	}
	return max - 1
}
